#define _CRT_SECURE_NO_WARNINGS 1
#include"sort.h"
void swap(int& a1,int& a2) {
	int tmp = a1;
	a1 = a2;
	a2 = tmp;
}
void BulleSort(int* arr,size_t n) {
	for (int i = n; i > 0 ; i--) {
		for (int j = 0; j < i-1; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);
			}
		}
	}
}


void QuickSort(int* arr, int left,int right) {
	if (left >= right) {
		return;
	}
	int begin = left, end = right;
	int keyi = left;
	while (begin < end) {
		if (begin<end && arr[end]>= arr[keyi]) {
			end--;
		}
		if (begin < end && arr[begin] <= arr[keyi]) {
			begin++;
		}
		swap(arr[begin], arr[end]);
		
	}
	swap(arr[keyi], arr[begin]);
	keyi = begin;
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}


int PartSort(int* a, int left, int right) {
	int keyi = left;
	int begin = left, end = right ;
	while (begin < end) {
		while (begin < end && a[keyi] <= a[end]) {
			end--;
		}
		while (begin < end && a[keyi] >= a[begin]) {
			begin++;
		}
		swap(a[begin], a[end]);
	}
	swap(a[keyi], a[begin]);
	return begin;
}

void QuickSortNoR(int* a, int left, int right) {
	stack<int> st;

	st.push(right);
	st.push(left);
	while (!st.empty()) {
		int begin = st.top();
		st.pop();
		int end = st.top();
		st.pop();

		int keyi = PartSort(a, begin, end);
		if (keyi + 1 < end) {
			st.push(end);
			st.push(keyi + 1);
		}
		if (keyi - 1 > begin) {
		st.push(keyi - 1);
		st.push(begin);
		}
	}


};

void insertSort(int* a, int size) {
	for (int i = 0; i < size - 1; i++) {
		int end = i;
		int tmp = a[end+1];
		while (end >= 0) {
			if (a[end] > tmp) {
				a[end + 1] = a[end];
				end--;
			}
			else {
				break;
			}
		}
		a[end+1] = tmp;
	}
}

void _MergeSort(int* a, int* tmp, int left, int right) {
	if (left == right) {
		return;
	}
	int mid = (left + right) / 2;
	_MergeSort(a, tmp, left, mid);
	_MergeSort(a, tmp, mid+1, right);

	
	int begin1 = left, end1 = mid;
	int i = left;
	int begin2 = mid + 1, end2 = right;

	
	while (begin1 < end1 && begin2 < end2) {
		if (a[begin1] < a[begin2]) {
			tmp[i++] = a[begin2++];
		}
		else {
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 < end1) {
		tmp[i++] = a[begin1++];
	}
	while (begin2 < end2) {
		tmp[i++] = a[begin2++];
	}
	memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));

}
void MergeSort(int* a, int size) {
	int* tmp = new int[size];

}


